/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 回文分隔 给定字符串s,将s进行分割，使得每个子串均为回文，求最小回文分割数。
 *  例如，输入s = "aab", Return 1 since the palindrome partitioning
 *  ["aa","b"] could be produced using 1 cut.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class PalindromePartitioningII {

    public int minCut(String s) {
        int len = s.length();
        //记录s[i]到字符串结尾的回文分隔数
        int dp[] = new int[len+1];
        boolean isPal[][] = new boolean[len][len];
        //初始化从i到结束的字符串的回文分隔
        for(int i=0;i<=len;i++){
            dp[i] = len-i-1;
        }
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                //判断i到j是否为回文，如是，更新最小回文
                if(s.charAt(i)==s.charAt(j) && (j-i<2 || isPal[i+1][j-1])){
                    isPal[i][j] = true;
                    //dp[i] 取dp[i]与dp[j+1]+的较小值        
                            dp[i] = Math.min(dp[i], dp[j+1]+1);
                }
            }
        }
        return dp[0];
    }
}
